package 回文子串专题;

/**
 * https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
 * 让字符串成为回文串的最小插入次数. 没说要要插入啥字母
 */
public class likou1312 {

    // 没说要要插入啥字母, 所以不用遍历字母表
    // 练习
    public int minInsertions(String s) {
        int n = s.length();
        // 表示 (i, j) 这段区间内所有让字符串成为回文串的次数中的最小插入次数
        int[][] dp = new int[n][n];
        // 无需初始化, 但是 i <= j. 从下往上, 从左往右遍历
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i == j) dp[i][j] = 0;
                    else if(i + 1 == j) dp[i][j] = 0; // 都是无需插入
                    else dp[i][j] = dp[i + 1][j - 1];
                }else {
                    // 二者中的最小值 + 1. 也就是两边插入一个 s.charAt(i) 或者是 s.charAt(j) 字符
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }

}
